import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-04-12
 * Time: 9:35
 */
public class Demo3 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        HashMap<String, Integer> hash1 = new LinkedHashMap<>();
        for (int i = 0; i < words.length; i++) {
            hash1.put(words[i], hash1.getOrDefault(words[i], 0) + 1);

        }
        int len = words[0].length();
        for (int i = 0; i < len; i++) {
            HashMap<String, Integer> hash2 = new LinkedHashMap<>();
            int count = 0;
            for (int right = 0, left = 0; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);

                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                if (right - left + 1 > len * words.length) {
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                if (count == words) {
                    list.add(left);
                }


            }
        }

        return list;
    }
}
